func numSquares(n int) int {
    /*
        力扣 279
        1. 定义
            dp[j] 表示 由完全平方数组成j最少的个数是dp[j]

        2. 递推公式
            dp[j] = min(dp[j], dp[j-coins[i]]+1)

        3. 初始化
            dp[0]=0
            dp[1-j] = max
        
        4. 遍历顺序
            组合型，完全背包问题
            先遍历物品，再遍历背包

        5. 推到dp数组

    */
    dp := make([]int, n+1)
    pingFangNumList := make([]int, n+1)
    for i:=1; i<len(dp); i++  {
        dp[i] = math.MaxInt
        pingFangNumList[i] = i*i
    }
    for _, v := range pingFangNumList {
        for j:=v; j<=n; j++ {
            if dp[j-v] != math.MaxInt {
                dp[j] = min(dp[j], dp[j-v]+1)
            }
        }
    }
    return dp[n]
}

func min(a, b int) int {
    if a>b {
        return b
    }
    return a
}

// 代码随想录版本
func numSquares(n int) int {
    /*
        1. 定义
            dp[j] 表示 由完全平方数组成j最少的个数是dp[j]

        2. 递推公式
            dp[j] = min(dp[j], dp[j-coins[i]]+1)

        3. 初始化
            dp[0]=0
            dp[1-j] = max
        
        4. 遍历顺序
            组合型，完全背包问题
            先遍历物品，再遍历背包

        5. 推到dp数组
            0 1
        1   0 M

    */
    dp := make([]int, n+1)
    for i:=1; i<len(dp); i++  {
        dp[i] = math.MaxInt
    }
    for i:=1; i*i<=n; i++ {
        for j:=i*i; j<=n; j++ {
            if dp[j-i*i] != math.MaxInt {
                dp[j] = min(dp[j], dp[j-i*i]+1)
            }
        }
    }
    return dp[n]
}

func min(a, b int) int {
    if a>b {
        return b
    }
    return a
}

